package mo.offer_version2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L38 {

    private List<String> res = new ArrayList<>();
    private boolean[] visited;

    public String[] permutation(String s) {
        int n = s.length();
        visited = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        backtrack(arr, 0, n, new StringBuilder());
        int size = res.size();
        String[] ret = new String[size];
        for (int i = 0; i < size; i++) {
            ret[i] = res.get(i);
        }
        return ret;
    }

    private void backtrack(char[] arr, int i, int n, StringBuilder builder) {
        if (i == n) {
            res.add(builder.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (visited[j] ||  (j > 0 && !visited[j-1] && arr[j-1] == arr[j])) {
                continue;
            }
            visited[j] = true;
            builder.append(arr[j]);
            backtrack(arr, i+1, n, builder);
            builder.deleteCharAt(builder.length()-1);
            visited[j] = false;
        }
    }

    public static void main(String[] args) {
        L38 test = new L38();
        System.out.println(Arrays.toString(test.permutation("abc")));
    }


}
